from collections import Counter


class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        stat1 = 0
        count = Counter({stat1: 1})
        ans = 0
        for ch in word:
            a = ord(ch) - 97
            stat1 ^= (1 << a)

            # 没有出现奇数次
            if stat1 in count:
                ans += count[stat1]

            # 1个奇数次
            for i in range(10):
                stat2 = stat1 ^ (1 << i)
                ans += count[stat2]

            count[stat1] += 1

            # print(ch, bin(stat1), "->", ans)

        return ans


if __name__ == "__main__":
    print(Solution().wonderfulSubstrings("aba"))  # 4
    print(Solution().wonderfulSubstrings("aabb"))  # 9
    print(Solution().wonderfulSubstrings("he"))  # 2
